1. Field of the Invention
The invention relates in general to a decompression circuit, and more particularly to a Lempel-Ziv-Markov chain-Algorithm (LZMA) decompression circuit and associated decompression method.
2. Description of the Related Art
In a compression operation using the Lempel-Ziv-Markov chain-Algorithm (LZMA), a repeating string is compressed into a distance-length pair. For example, a string “ABCDABCE” is compressed into “A, B, C D (4, 3), E”, where (4, 3) is referred to as a distance-length pair that represents three literals (i.e., A, B, and C) (length) of four previous literals (distance). Another compression operation is then performed to generate compressed data. In a decompression process, the compressed data is decompressed, by binary arithmetic coding (BAC), into “A, B, C, D, (4, 3), E”, which is then restored into “ABCDABCE” using an LZ77 decompression operation. When decompressing a next literal (commonly referred to as “delta literal”, which is “E” in this example) of the length-distance pair using the BAC, a previous literal (the seventh literal “C” in this example) and the next literal (the fourth literal “D” in this example) of the string corresponding to the distance-length pair are used. Therefore, when decompressing “E” using the BAC, “C” and “D” can only be provided to a front-end for the BAC decompression after the distance-length pair (4, 3) is decompressed by the LZ77 operation, leading to reduced decompression efficiency. Further, compression/decompression utilizing the LZMA is all implemented through software.